Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

题目大意：给定整数n，返回n对括号所有的合法组合

题目难度：Medium

import java.util.*;

/**
 * Created by gzdaijie on 16/5/19
 * 递归解法,tmp记录构造的字符串
 */
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        StringBuilder tmp = new StringBuilder();
        recursionGenerate(result, tmp, n, n);
        return result;
    }

    /**
     * 递归构造组合方式
     * @param result 记录结果
     * @param tmp 记录临时组合的字符串
     * @param left 记录左括号剩余个数
     * @param right 记录右括号剩余个数
     */
    private void recursionGenerate(List<String> result, StringBuilder tmp, int left, int right) {
        if (left == 0 && right == 0) {
            result.add(tmp.toString());
            return;
        }
        // 还有剩余的左括号,添加左括号递归
        if (left > 0) {
            tmp.append('(');
            recursionGenerate(result, tmp, left - 1, right);
            tmp.setLength(tmp.length() - 1);
        }
        // 还有剩余的右括号,且剩余的右括号多于左括号,添加右括号递归
        if (right > 0 && left < right) {
            tmp.append(')');
            recursionGenerate(result, tmp, left, right - 1);
            tmp.setLength(tmp.length() - 1);
        }
    }
}